package com.zlk.algorithm.algorithm.sort.heap;

import org.junit.Test;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @program: algorithm
 * @ClassName LineCoverMax
 * @description:线段最大重合问题
 * 多个闭区间线段，统计最大重合数
 * @author: slfang
 * @create: 2024-01-24 08:59
 * @Version 1.0
 **/
public class LineCoverMax {

    @Test
    public void test1(){
        int testTimes = 1000;
        int lines=100;
        //区间
        int l = 0;
        int r = 200;
        for (int i = 0; i < testTimes; i++) {
            int[][] ints = generateLines(lines, l, r);
            int maxCover = findMaxCover(ints);

            int maxCoverObj = findMaxCoverObj(ints);
            int max = findMax(ints);
            if(maxCoverObj!=max){
                System.out.println("fail");
                return ;
            }
        }
        System.out.println("success");

    }


    /**
     *
     * @param lines
     * @return
     */
    private int findMax(int[][] lines) {
        //找|到所以选段区间的极限
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < lines.length; i++) {
            min = Math.min(min, lines[i][0]);
            max = Math.max(max, lines[i][1]);
        }
        int cover = 0;
        for (double i = min+0.5; i < max; i+=1) {
            int count = 0;
            for (int[] ints : lines) {
                if(ints[0]<i&&ints[1]>i){
                    count++;
                }
            }
            cover = Math.max(cover,count);
        }
        return cover;
    }

    /**
     * 与findMaxCover 一样，只不过该方法是根据实体类处理
     * @param m
     */
    private int findMaxCoverObj(int[][] m) {
        PriorityQueue<Line> queue = new PriorityQueue<Line>((a,b)-> a.start-b.start);
        //PriorityQueue<Line> queue = new PriorityQueue<Line>(new StartComparator());
        PriorityQueue<Integer> priorityQueue = new PriorityQueue();
        for (int[] lineArr : m) {
            queue.add(new Line(lineArr[0],lineArr[1]));
        }
        int max = 0;
        while (!queue.isEmpty()){
            Line curr = queue.poll();
            while (!priorityQueue.isEmpty()&&priorityQueue.peek()<=curr.start){
                priorityQueue.poll();
            }
            priorityQueue.add(curr.end);
            max = Math.max(max,priorityQueue.size());
        }
        return max;
    }

    public static class StartComparator implements Comparator<Line> {
        @Override
        public int compare(Line o1, Line o2) {
            return o1.start - o2.start;
        }

    }


    /**
     * 不是实体类方法
     * 1、对左区间开始排序
     * 2、遍历排序的线段，查找堆中是否存在小于等于左区间的弹出，然后加入当前线段右区间，统计堆中数量，遍历取最大就是目标值
     * 时间复杂度 nLogN
     * @param m
     * @return
     */
    private int findMaxCover(int[][] m) {
//        Arrays.sort(ints, new Comparator<int[]>() {
//            @Override
//            public int compare(int[] o1, int[] o2) {
//                return o1[0]-o2[0];
//            }
//        });
        Arrays.sort(m,(a,b) -> (a[0]-b[0]));
        //二维数组的遍历
//        for (int i = 0; i < m.length; i++) {//控制行数
//            for (int j = 0; j <m[i].length ; j++) {//控制列数
//
//            }
//        }
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int max = 0;
        for (int[] line : m) {
            while (!heap.isEmpty() && heap.peek() <= line[0]) {
                heap.poll();
            }
            heap.add(line[1]);
            max = Math.max(max, heap.size());
        }
        return max;
    }

    public static class Line {
        public int start;
        public int end;

        public Line(int s, int e) {
            start = s;
            end = e;
        }

    }

    /**
     * N代表有多少个线段意思  二维数组中就是多少行
     * ans[i][0] 代表线段的起始位置
     * ans[i][1] 代表线段的结束位置
     * @param N
     * @param L
     * @param R
     * @return
     */
    public static int[][] generateLines(int N, int L, int R) {
        int size = (int) (Math.random() * N) + 1;
        int[][] ans = new int[size][2];
        for (int i = 0; i < size; i++) {
            int a = L + (int) (Math.random() * (R - L + 1));
            int b = L + (int) (Math.random() * (R - L + 1));
            if (a == b) {
                b = a + 1;
            }
            ans[i][0] = Math.min(a, b);
            ans[i][1] = Math.max(a, b);
        }
        return ans;
    }




}
